package me.ingxin.android.router.compiler.util

/**
 * Created by ingxin on 2022/4/14
 */
class DirectedAcyclicGraph<T> {

    /**顶点入度边表示DAG*/
    private val graph = LinkedHashMap<T, ArrayList<T>?>()
    private val sortResult = ArrayList<T>()
    private val sortTmpMarked = LinkedHashSet<T>()

    /**
     * 增加一个顶点
     * @param node 顶点
     */
    fun addNode(node: T) {
        if (!graph.containsKey(node)) {
            graph[node] = null
        }
    }

    /**
     * 是否包含顶点
     * @param node 查询的顶点
     * @return true包含，否则不包含
     */
    fun contains(node: T): Boolean {
        return graph.containsKey(node)
    }

    /**
     * 增加一条边
     *
     * @param node         终点
     * @param incomingEdge 起点
     */
    fun addEdge(node: T, incomingEdge: T) {
        if (!graph.containsKey(node) || !graph.containsKey(incomingEdge)) {
            throw IllegalArgumentException("All nodes must be present in the graph before being added as an edge")
        }
        var edges = graph[node]
        if (edges == null) {
            edges = ArrayList()
            graph[node] = edges
        }
        edges.add(incomingEdge)
    }

    /**
     * 获取顶点的入度边
     * @param node 查询的顶点
     */
    fun getIncomingEdges(node: T): List<T>? {
        return graph[node]
    }

    /***
     * 获顶点的出度边
     * @param node 查询的顶点
     */
    fun getOutgoingEdges(node: T): List<T>? {
        var result: ArrayList<T>? = null
        for (key in graph.keys) {
            val edges = graph[key]
            if (edges != null && edges.contains(node)) {
                if (result == null) {
                    result = ArrayList()
                }
                result.add(key)
            }
        }
        return result
    }

    /**
     * 检测是否有出度边
     */
    fun hasOutgoingEdges(node: T): Boolean {
        for (key in graph.keys) {
            val edges = graph[key]
            if (edges != null && edges.contains(node)) {
                return true
            }
        }
        return false
    }

    fun clear() {
        for (key in graph.keys) {
            val edges = graph[key]
            edges?.clear()
        }
        graph.clear()
    }

    /**
     * 获取拓扑排序后的结果
     */
    fun getSortedList(): ArrayList<T> {
        sortResult.clear()
        sortTmpMarked.clear()
        for (key in graph.keys) {
            dfs(key, sortResult, sortTmpMarked)
        }
        return sortResult
    }

    /**
     * 递归排序
     * <p>
     *     当退出方法时时说明该顶点的入度为0了
     * </p>
     */
    private fun dfs(node: T, result: ArrayList<T>, tmpMarked: HashSet<T>) {
        if (result.contains(node)) {
            return
        }
        if (tmpMarked.contains(node)) {
            val sb = StringBuilder()
            tmpMarked.forEach {
                sb.append(it.toString()).append("->")
            }
            sb.append(node)
            throw DependenceException("This graph contains cyclic dependencies, $sb")
        }

        tmpMarked.add(node)
        val edges = graph[node]
        if (edges != null) {
            for (item in edges) {
                dfs(item, result, tmpMarked)
            }
        }
        //遍历结束，说明已经遍历完node顶点，此时入度为0，可以进行排序列表
        tmpMarked.remove(node)
        result.add(node)
    }

    fun size(): Int = graph.size

}